COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input twimac
C00003 00003	\NN1.  \[1] Introduction.
C00006 00004	\N4.  \[2] The data structures.
C00010 00005	\N7.  \[3] Outputting.
C00016 00006	\N12.  \[4] Sorting.
C00019 00007	\N16.  \[5] Inputting.
C00023 00008	\N20.  \[6] The main program.
C00024 00009	\N21.  \[7] Index.
C00025 00010	\inx
C00027 00011	\fin
C00029 ENDMK
C⊗;
\input twimac
% This program by D. E. Knuth is not copyrighted and can be used freely.

% Here is TeX material that gets inserted after \input webmac
\def\title{GRADES}
\pageno=0

\NN1.  \[1] Introduction.
This is a simple program hacked together to process the comp grades
in January 1987. I~revised it in May of that year, by adding the
sorting phase so that histogram computation is easy.

The input data starts with a line that describes the exam,
followed by the data sets for individual graders.
Each data set begins with a special line that says `\.*' in column~1,
followed by the grader's name (maximum of nine letters), followed by
another `\.*', followed by
the section number ($1\to5$), a space, and the grader number($1\to2$). (Each of
the
five sections is supposed to have two graders.)
After this special line, the grades themselves appear on subsequent
lines; they consist of two integer numbers, the student number ($0\to99$)
and the grade.

For example, the input data might begin like this:
$$\vbox{\halign{\tt#\hfil\cr
Theory Comp, January 14, 1987\cr
*Ross*4 1\cr
11 27\cr
32 30\cr
17 33\cr}}$$
meaning that Ross was the first grader of part~4, and that student~11 had
27~points, etc.

\α%
}\FI

\M2. Here's an outline of the entire Pascal program:

\Y\P\4\&{program}\1\  \37$\\{grades}(\\{input},\39\\{output})$;\6
\4\&{const} \37\X3:Constants in the outer block\X\6
\4\&{type} \37\X4:Types in the outer block\X\6
\4\&{var} \37\X5:Global variables\X\7
\&{begin} \37\X6:Set initial values\X;\6
\X20:The main program\X;\6
\&{end}.\par
\α%
}\FI

\M3. When the scores of two graders differ by more than \\{tol},
the grades will be flagged in the output.

\Y\P$\4\X3:Constants in the outer block\X\S$\6
$\\{tol}=3$;\par
\U section~2.\α%
}\FI

\N4.  \[2] The data structures.
Almost all the relevant info is stored in a big array \|G.
The first subscript indicates the student number ($0\to99$).
The second subscript indicates the section number ($1\to5$).
The final subscript indicates the grader number ($1\to2$).
The array entry is the grade.

There also are boolean arrays that tell whether there exists any
data for a given student number or a given $(\\{section},\\{grader})$ pair.

\Y\P$\4\X4:Types in the outer block\X\S$\6
$\\{student\_number}=0\to99$;\6
$\\{section\_number}=1\to5$;\6
$\\{grader\_number}=1\to2$;\6
$\\{g\_name}=$\1\5
\&{array} $[1\to9]$ \1\&{of}\5
\\{char};\2\2\par
\U section~2.\α%
}\FI

\M5. \P$\X5:Global variables\X\S$\6
\4\|g: \37\&{array} $[\\{student\_number},\39\\{section\_number},\39\\{grader%
\_number}]$ \1\&{of}\5
\\{integer};\C{the grades}\2\6
\4\\{stud}: \37\&{array} $[\\{student\_number}]$ \1\&{of}\5
\\{boolean};\C{is there a grade for this student?}\2\6
\4\\{grad}: \37\&{array} $[\\{section\_number},\39\\{grader\_number}]$ \1\&{of}%
\5
\\{boolean};\C{are there any grades from this grader?}\2\6
\4\\{name}: \37\&{array} $[\\{section\_number},\39\\{grader\_number}]$ \1\&{of}%
\5
\\{g\_name};\2\6
\4\\{totals}: \37\&{array} $[\\{section\_number},\39\\{grader\_number}]$ \1%
\&{of}\5
\\{integer};\C{column totals}\2\6
\4\|s: \37\\{student\_number};\6
\4\|k: \37\\{section\_number};\6
\4\|l: \37\\{grader\_number};\6
\4\\{cur\_name}: \37\\{g\_name};\6
\4\|t: \37\\{integer};\par
\A sections~12 and~19.
\U section~2.\α%
\βg_name 4 =\&{array}
\βgrader_number 4 =$1\to2$
\βsection_number 4 =$1\to5$
\βstudent_number 4 =$0\to99$
}\FI

\M6. \P$\X6:Set initial values\X\S$\6
\&{for} $\|s\K0\mathrel{\&{to}}99$ \1\&{do}\5
$\\{stud}[\|s]\K\\{false}$;\2\6
\&{for} $\|k\K1\mathrel{\&{to}}5$ \1\&{do}\6
\&{for} $\|l\K1\mathrel{\&{to}}2$ \1\&{do}\5
$\\{grad}[\|k,\39\|l]\K\\{false}$;\2\2\6
\&{for} $\|s\K0\mathrel{\&{to}}99$ \1\&{do}\6
\&{for} $\|k\K1\mathrel{\&{to}}5$ \1\&{do}\6
\&{for} $\|l\K1\mathrel{\&{to}}2$ \1\&{do}\5
$\|g[\|s,\39\|k,\39\|l]\K-1$;\2\2\2\par
\A section~13.
\U section~2.\α%
\βl 5 :\\{grader\_number}
\βk 5 :\\{section\_number}
\βs 5 :\\{student\_number}
\βgrad 5 :\&{array}
\βstud 5 :\&{array}
\βg 5 :\&{array}
}\FI

\N7.  \[3] Outputting.
The lines of output consist of 5 columns for student number, then
18 columns for each of the five sections, then 5 columns for the total score,
then five more to repeat the student number.

\Y\P$\4\X7:Output the arrays\X\S$\6
\X8:Write the subtitle line\X;\6
\X9:Write the grader names\X;\6
$\|m\K0$;\6
\&{for} $\|s\K0\mathrel{\&{to}}99$ \1\&{do}\6
\&{if} $\\{stud}[\|s]$ \1\&{then}\6
\&{begin} \37$\|m\K\|m+1$;\5
\X11:Write the grades for student \|s\X;\6
\X14:Rank the new grade among the previous ones\X;\6
\&{end};\2\2\6
\X10:Write the line of totals\X;\6
$\\{write\_ln}(\.{\'\ There\ were\ \'},\39\|m:1,\39\.{\'\ students\ altogether.%
\'})$;\5
\\{write\_ln};\5
\X15:Output the grades in rank order\X\par
\U section~20.\α%
\βm 19 :\\{integer}
\βs 5 :\\{student\_number}
\βstud 5 :\&{array}
}\FI

\M8. \P$\X8:Write the subtitle line\X\S$\6
$\\{write\_ln}(\.{\'\ \ \ \ \ \'},\39\.{\'--------A--------\ \'},\39\.{%
\'--------B--------\ \'},\39\.{\'--------C--------\ \'},\39\.{%
\'--------D--------\ \'},\39\.{\'--------E--------\ \'},\39\.{\'Total\'})$\par
\U section~7.\α%
}\FI

\M9. \P$\X9:Write the grader names\X\S$\6
$\\{write}(\.{\'\ \ \ \ \ \'})$;\6
\&{for} $\|k\K1\mathrel{\&{to}}5$ \1\&{do}\6
\&{for} $\|l\K1\mathrel{\&{to}}2$ \1\&{do}\6
\&{if} $\\{grad}[\|k,\39\|l]$ \1\&{then}\5
$\\{write}(\\{name}[\|k,\39\|l])$\6
\4\&{else} $\\{write}(\.{\'\ \#\#\#\#\#\#\#\ \'})$;\2\2\2\6
\\{write\_ln}\par
\U section~7.\α%
\βl 5 :\\{grader\_number}
\βk 5 :\\{section\_number}
\βname 5 :\&{array}
\βgrad 5 :\&{array}
}\FI

\M10. \P$\X10:Write the line of totals\X\S$\6
$\\{write}(\.{\'Total\'})$;\5
$\|t\K0$;\6
\&{for} $\|k\K1\mathrel{\&{to}}5$ \1\&{do}\6
\&{for} $\|l\K1\mathrel{\&{to}}2$ \1\&{do}\6
\&{if} $\\{grad}[\|k,\39\|l]$ \1\&{then}\6
\&{begin} \37$\|t\K\|t+\\{totals}[\|k,\39\|l]$;\5
$\\{write}(\\{totals}[\|k,\39\|l]:5,\39\.{\'\ \ \ \ \'})$;\6
\&{end}\6
\4\&{else} $\\{write}(\.{\'\ \ \ \ \ \ \ \ \ \'})$;\2\2\2\6
$\\{write\_ln}(\|t:5)$\par
\U section~7.\α%
\βt 5 :\\{integer}
\βl 5 :\\{grader\_number}
\βk 5 :\\{section\_number}
\βtotals 5 :\&{array}
\βgrad 5 :\&{array}
}\FI

\M11. \P$\X11:Write the grades for student \|s\X\S$\6
\&{begin} \37$\\{write}(\|s:2,\39\.{\':\ \ \'})$;\5
$\|t\K0$;\6
\&{for} $\|k\K1\mathrel{\&{to}}5$ \1\&{do}\6
\&{begin} \37\&{if} $\\{grad}[\|k,\391]$ \1\&{then}\5
$\\{write}(\|g[\|s,\39\|k,\391]:5,\39\.{\'\ \ \ \'})$\6
\4\&{else} $\\{write}(\.{\'\ \ \ \ \ \ \ \ \'})$;\2\6
\&{if} $\\{grad}[\|k,\391]\W\\{grad}[\|k,\392]\W(\\{abs}(\|g[\|s,\39\|k,\391]-%
\|g[\|s,\39\|k,\392])>\\{tol})$ \1\&{then}\5
$\\{write}(\.{\'*\'})$\6
\4\&{else} $\\{write}(\.{\'\ \'})$;\2\6
\&{if} $\\{grad}[\|k,\392]$ \1\&{then}\5
$\\{write}(\|g[\|s,\39\|k,\392]:5,\39\.{\'\ \ \ \ \'})$\6
\4\&{else} $\\{write}(\.{\'\ \ \ \ \ \ \ \ \ \'})$;\2\6
\&{end};\2\6
\&{for} $\|k\K1\mathrel{\&{to}}5$ \1\&{do}\6
\&{for} $\|l\K1\mathrel{\&{to}}2$ \1\&{do}\6
\&{if} $\\{grad}[\|k,\39\|l]$ \1\&{then}\5
$\|t\K\|t+\|g[\|s,\39\|k,\39\|l]$;\2\2\2\6
$\\{write\_ln}(\|t:5,\39\.{\'\ \ :\'},\39\|s:1)$;\6
\&{end}\par
\U section~7.\α%
\βt 5 :\\{integer}
\βl 5 :\\{grader\_number}
\βk 5 :\\{section\_number}
\βs 5 :\\{student\_number}
\βgrad 5 :\&{array}
\βg 5 :\&{array}
\βtol 3 =\&{const}
}\FI

\N12.  \[4] Sorting.
Straight insertion is plenty good for the small amount of data that
needs to be sorted.

\Y\P$\4\X5:Global variables\X\mathrel{+}\S$\6
\4\\{score}: \37\&{array} $[0\to100]$ \1\&{of}\5
\\{integer};\C{the $m$ scores known so far, 	preceded by $-1$}\2\6
\4\|j: \37$0\to100$;\C{loop index}\par
\α%
}\FI

\M13. \P$\X6:Set initial values\X\mathrel{+}\S$\6
$\\{score}[0]\K-1$;\C{sentinel to simplify the loop}\par
\α%
\βscore 12 :\&{array}
}\FI

\M14. At this point, $s$ is the $m$th student whose grades have been computed;
$t$ is the grade; and $m-1$ previous grades are in the \\{score} array.

\Y\P$\4\X14:Rank the new grade among the previous ones\X\S$\6
$\|j\K\|m-1$;\6
\&{while} $\|t<\\{score}[\|j]$ \1\&{do}\6
\&{begin} \37$\\{score}[\|j+1]\K\\{score}[\|j]$;\5
$\|j\K\|j-1$;\6
\&{end};\2\6
$\\{score}[\|j+1]\K\|t$\par
\U section~7.\α%
\βm 19 :\\{integer}
\βj 12 :$0\to100$
\βscore 12 :\&{array}
\βt 5 :\\{integer}
}\FI

\M15. \P$\X15:Output the grades in rank order\X\S$\6
\&{for} $\|j\K1\mathrel{\&{to}}\|m$ \1\&{do}\6
\&{begin} \37$\\{write}(\\{score}[\|j]:4)$;\6
\&{if} $\|j\mathbin{\&{mod}}20=0$ \1\&{then}\5
\\{write\_ln};\2\6
\&{end}\2\par
\U section~7.\α%
\βm 19 :\\{integer}
\βj 12 :$0\to100$
\βscore 12 :\&{array}
}\FI

\N16.  \[5] Inputting.
This program does very little more than input and output.
Since we've already seen how to do the output, only input remains.
Unfortunately, I always have trouble remembering how to do input
in Pascal, so this code is probably inelegant.

\Y\P$\4\X16:Input and output the title line\X\S$\6
\&{while} $\R\\{eoln}$ \1\&{do}\6
\&{begin} \37$\\{write}(\\{input}\↑)$;\5
$\\{get}(\\{input})$;\6
\&{end};\2\6
\\{read\_ln};\5
\\{write\_ln}\par
\U section~20.\α%
\βinput 2 \ε
}\FI

\M17. \P$\X17:Read a set of grades\X\S$\6
\&{begin} \37\X18:Read the grader's name into \\{cur\_name}\X;\6
$\\{read\_ln}(\|k,\39\|l)$;\5
$\\{name}[\|k,\39\|l]\K\\{cur\_name}$;\5
$\|t\K0$;\5
$\\{grad}[\|k,\39\|l]\K\\{true}$;\6
\&{while} $\R\\{eof}\W(\\{input}\↑\I\.{\'*\'})$ \1\&{do}\6
\&{begin} \37$\\{read\_ln}(\|s,\39\|n)$;\5
$\\{stud}[\|s]\K\\{true}$;\5
$\|t\K\|t+\|n$;\5
$\|g[\|s,\39\|k,\39\|l]\K\|n$;\6
\&{end};\2\6
$\\{totals}[\|k,\39\|l]\K\|t$;\6
\&{end}\par
\U section~20.\α%
\βn 19 :\\{integer}
\βt 5 :\\{integer}
\βcur_name 5 :\\{g\_name}
\βl 5 :\\{grader\_number}
\βk 5 :\\{section\_number}
\βs 5 :\\{student\_number}
\βtotals 5 :\&{array}
\βname 5 :\&{array}
\βgrad 5 :\&{array}
\βstud 5 :\&{array}
\βg 5 :\&{array}
\βinput 2 \ε
}\FI

\M18. At this point the \\{input} file should contain the asterisk at the
beginning of a data set. We center the name so that it will look nice.

\Y\P$\4\X18:Read the grader's name into \\{cur\_name}\X\S$\6
$\\{read}(\\{ch})$;\ \&{if} $\\{ch}\I\.{\'*\'}$ \1\&{then}\5
$\\{write}(\\{tty},\39\.{\'Missing\ *!\'})$;\2\6
$\|n\K0$;\ \&{while} $\\{input}\↑\I\.{\'*\'}$ \1\&{do}\6
\&{begin} \37$\|n\K\|n+1$;\5
$\\{read}(\\{cur\_name}[\|n])$;\6
\&{end};\2\6
$\\{read}(\\{ch})$;\6
\&{if} $\|n<9$ \1\&{then}\6
\&{begin} \37\&{for} $\|m\K\|n\mathrel{\&{downto}}1$ \1\&{do}\5
$\\{cur\_name}[\|m+(8-\|n)\mathbin{\&{div}}2]\K\\{cur\_name}[\|m]$;\2\6
\&{for} $\|m\K1\mathrel{\&{to}}(8-\|n)\mathbin{\&{div}}2$ \1\&{do}\5
$\\{cur\_name}[\|m]\K\.{\'\ \'}$;\2\6
\&{for} $\|m\K1\mathrel{\&{to}}(11-\|n)\mathbin{\&{div}}2$ \1\&{do}\5
$\\{cur\_name}[10-\|m]\K\.{\'\ \'}$;\2\6
\&{end}\2\par
\U section~17.\α%
\βch 19 :\\{char}
\βn 19 :\\{integer}
\βm 19 :\\{integer}
\βcur_name 5 :\\{g\_name}
\βinput 2 \ε
}\FI

\M19. \P$\X5:Global variables\X\mathrel{+}\S$\6
\4$\|m,\39\|n$: \37\\{integer};\6
\4\\{ch}: \37\\{char};\par
\α%
}\FI

\N20.  \[6] The main program.
The pieces of the puzzle fit together easily as follows.

\Y\P$\4\X20:The main program\X\S$\6
\X16:Input and output the title line\X;\6
\&{while} $\R\\{eof}$ \1\&{do}\5
\X17:Read a set of grades\X;\2\6
\X7:Output the arrays\X\par
\U section~2.\α%
}\FI

\N21.  \[7] Index.
Here are the quantities declared and/or used in the program.
(The uses of single-letter variables aren't indexed.)
\α%
}\FI


\inx
\:\\{abs}, 11.
\:\\{boolean}, 5.
\:\\{ch}, 18, \[19].
\:\\{char}, 4, 19.
\:\\{cur\_name}, \[5], 17--18.
\:\\{eof}, 17, 20.
\:\\{eoln}, 16.
\:\\{false}, 6.
\:\|{g}, \[5].
\:\\{g\_name}, \[4], 5.
\:\\{get}, 16.
\:\\{grad}, \[5], 6, 9--11, 17.
\:\\{grader\_number}, \[4], 5.
\:\\{grades}, \[2].
\:\\{input}, \[2], 16--18.
\:\\{integer}, 5, 12, 19.
\:\|{j}, \[12].
\:\|{k}, \[5].
\:\|{l}, \[5].
\:\|{m}, \[19].
\:\|{n}, \[19].
\:\\{name}, \[5], 9, 17.
\:\\{output}, \[2].
\:\\{read}, 18.
\:\\{read\_ln}, 16--17.
\:\|{s}, \[5].
\:\\{score}, \[12], 13--15.
\:\\{section\_number}, \[4], 5.
\:\\{stud}, \[5], 6--7, 17.
\:\\{student\_number}, \[4], 5.
\:\|{t}, \[5].
\:\\{tol}, \[3], 11.
\:\\{totals}, \[5], 10, 17.
\:\\{true}, 17.
\:\\{tty}, 18.
\:\\{write}, 9--11, 15--16, 18.
\:\\{write\_ln}, 7--11, 15--16.
\fin
\:\X3:Constants in the outer block\X
\U section~2.
\:\X5, 12, 19:Global variables\X
\U section~2.
\:\X16:Input and output the title line\X
\U section~20.
\:\X7:Output the arrays\X
\U section~20.
\:\X15:Output the grades in rank order\X
\U section~7.
\:\X14:Rank the new grade among the previous ones\X
\U section~7.
\:\X17:Read a set of grades\X
\U section~20.
\:\X18:Read the grader's name into \\{cur\_name}\X
\U section~17.
\:\X6, 13:Set initial values\X
\U section~2.
\:\X20:The main program\X
\U section~2.
\:\X4:Types in the outer block\X
\U section~2.
\:\X9:Write the grader names\X
\U section~7.
\:\X11:Write the grades for student \|s\X
\U section~7.
\:\X10:Write the line of totals\X
\U section~7.
\:\X8:Write the subtitle line\X
\U section~7.
\con